package com.ease.context.algorithm;

import com.ease.context.datastructure.ChainNode;

/**
 * 
 * @author nathanleewei
 * 
 */
public abstract class Chains {

	/**
	 * 用两个指针,一个的步长为 1,另外一个的为 2,从表头开始一起往前走,如果相遇,表明有环路,否则就是没有了。
	 * 
	 * @param <T>
	 * @param singleLinkedList
	 * @return
	 */
	public static <T extends ChainNode<T>> boolean hasCircle(T chainNode) {

		if (null != chainNode && null != chainNode.next() && null != chainNode.next().next()) {
			T stepOne = chainNode.next();
			T stepTwo = chainNode.next().next();

			while (null != stepOne && null != stepTwo) {
				if (stepOne.equals(stepTwo)) {
					return true;
				}
				stepOne = stepOne.next();
				stepTwo = stepTwo.next();
				if (null != stepTwo) {
					stepTwo = stepTwo.next();
				}
			}

		}
		return false;
	}

	/**
	 * 
	 * @param <T>
	 * @param chainNode
	 * @param callback
	 * @return
	 */
	public static <T extends ChainNode<T>> T reverse(T chainNode, ChainNodeVisitCallback<T> callback) {

		if (null != chainNode) {
			T currentChainNode = null;
			T nextChainNode = null;
			while (null != chainNode) {
				nextChainNode = currentChainNode;
				currentChainNode = chainNode;

				chainNode = chainNode.next();

				currentChainNode.next(nextChainNode);

				callback.visit(currentChainNode, nextChainNode);
			}
			return currentChainNode;
		}
		return null;

	}

	/**
	 * 
	 * @param <T>
	 * @param chainNode
	 * @return
	 */
	public static <T extends ChainNode<T>> T last(T chainNode) {
		while (null != chainNode) {
			if (null == chainNode.next()) {
				return chainNode;
			}
			chainNode = chainNode.next();
		}

		return null;
	}

	/**
	 * 
	 * @param <T>
	 * @param chainNode
	 * @return
	 */
	public static <T extends ChainNode<T>> int length(T chainNode) {
		if (null != chainNode) {
			if (hasCircle(chainNode)) {
				return -1;
			} else {
				int length = 0;

				while (null != chainNode) {
					length++;
					chainNode = chainNode.next();
				}

				return length;
			}
		}
		return 0;
	}

}
